procedure kuhn();

var
	i, j, tt : longint;
	used, used1 : array[0..MAXN] of boolean;

	function tryKuhn(v : longint) : boolean;

	var
		i, tt, tto : longint;
	
	begin
		if v < 1 then begin
			result := true;
			exit;
		end;
		if used[v] then begin
			result := false;
			exit;
		end;
		used[v] := true;
		tt := length(g[v]) - 1;
		for i := 0 to tt do begin
			tto := g[v][i];
			if (mt[tto] = -1) or tryKuhn(mt[tto]) then begin
				mt[tto] := v;
				result := true;
				exit;
			end;
		end;
		result := false;
	end;

begin
	ans := 0;
	fillchar(mt, sizeof(mt), -1);
	for i := 1 to n do begin
		tt := length(g[i]) - 1;
		for j := 0 to tt do
			if mt[g[i][j]] = -1 then begin
				mt[g[i][j]] := i;
				used1[i] := true;
				break;
			end;
	end;
	for i := 1 to n do begin
		if used1[i] then continue;
		fillchar(used, sizeof(used), 0);
		tryKuhn(i);
	end;
	for i := 1 to m do
		if mt[i] <> -1 then begin
			inc(ans);
			a[ans][1] := mt[i];
			a[ans][2] := i;
		end;
end;
